package demo

type Space struct {
	isCertained     bool
	value           int
	possibleNumbers []int
}
type position struct {
	x int
	y int
}

func Sudoku(array [9][9]int) ([9][9]int,bool) {
	ss := &[9][9]*Space{}
	know := 0
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if array[i][j] != 0 {
				addFoundNum(ss, array[i][j], i, j, &know)
			} else {
				ss[i][j] = new(Space)
			}
		}
	}
	ok:=SudokuRecursion(ss, &know)
	if !ok{
		//需要高级解法
		formatPossipossibleNumbers(ss)
	}
	var res = [9][9]int{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			res[i][j] = ss[i][j].value
		}
	}
	return res,ok
}

func formatPossipossibleNumbers(array *[9][9]*Space) {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if !array[i][j].isCertained{
				sum:=0
				for _,v:=range array[i][j].possibleNumbers{
					sum=sum*10+v
				}
				array[i][j].value=sum
			}
		}
	}
}

//迭代法求结果
func SudokuRecursion(array *[9][9]*Space, known *int) bool{
	if *known >= 81 {
		return true
	}
	temp := *known
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if !array[i][j].isCertained {
				a := checkRowColumn(array, i, j)
				b := checkQuac(array, i, j)
				c := removeNotDuplicatedNums(a, b)
				if len(array[i][j].possibleNumbers) != 0 {
					c = removeNotDuplicatedNums(c, array[i][j].possibleNumbers)
				}
				if len(c) == 1 {
					addFoundNum(array, c[0], i, j, known)
				} else {
					array[i][j].possibleNumbers = c
				}
			}
		}
	}
	if temp == *known {
		ok:=checkRowColumnStrictly(array, known)
		if !ok{
			return false
		}
	}
	return SudokuRecursion(array, known)
}

//给(i,j)位置的空格填入x数字
func addFoundNum(array *[9][9]*Space, x, i, j int, know *int) {
	s := &Space{
		isCertained:     true,
		value:           x,
		possibleNumbers: nil,
	}
	array[i][j] = s
	*know++
}

//检查点(x,y)行列，返回可能存在的解
func checkRowColumn(array *[9][9]*Space, x, y int) []int {
	record := make([]int, 10)
	res := []int{}
	if array[x][y].isCertained {
		return res
	}
	for i := 0; i < 9; i++ {
		if i == y || array[x][i].value == 0 {
			continue
		} else {
			record[array[x][i].value]++
		}
	}
	for i := 0; i < 9; i++ {
		if i == x || !array[i][y].isCertained {
			continue
		} else {
			record[array[i][y].value]++
		}
	}
	for i := 1; i < 10; i++ {
		if record[i] == 0 {
			res = append(res, i)
		}
	}
	return res
}

//检查3x3的约束，返回可能存在的解
func checkQuac(array *[9][9]*Space, x, y int) []int {
	if array[x][y].isCertained {
		return []int{}
	}
	if x < 3 && x >= 0 {
		if y < 3 && y >= 0 {
			return checkItoa(array, 0, 0)
		} else if y < 6 && y >= 3 {
			return checkItoa(array, 0, 3)
		} else {
			return checkItoa(array, 0, 6)
		}
	} else if x < 6 && x >= 3 {
		if y < 3 && y >= 0 {
			return checkItoa(array, 3, 0)
		} else if y < 6 && y >= 3 {
			return checkItoa(array, 3, 3)
		} else {
			return checkItoa(array, 3, 6)
		}
	} else {
		if y < 3 && y >= 0 {
			return checkItoa(array, 6, 0)
		} else if y < 6 && y >= 3 {
			return checkItoa(array, 6, 3)
		} else {
			return checkItoa(array, 6, 6)
		}
	}

}

//辅助检查3x3
func checkItoa(array *[9][9]*Space, x_first, y_first int) []int {
	record := make([]int, 10)
	res := []int{}

	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if array[x_first+i][y_first+j].isCertained {
				record[array[x_first+i][y_first+j].value]++
			}
		}
	}

	for i := 1; i < 10; i++ {
		if record[i] == 0 {
			res = append(res, i)
		}
	}
	return res
}

//检查行列，严格
func checkRowColumnStrictly(array *[9][9]*Space, know *int) bool{
	temp:=*know
	checkOnyOneForArea(array, 0, 0, know)
	checkOnyOneForArea(array, 0, 3, know)
	checkOnyOneForArea(array, 0, 6, know)
	checkOnyOneForArea(array, 3, 0, know)
	checkOnyOneForArea(array, 3, 3, know)
	checkOnyOneForArea(array, 3, 6, know)
	checkOnyOneForArea(array, 6, 0, know)
	checkOnyOneForArea(array, 6, 3, know)
	checkOnyOneForArea(array, 6, 6, know)

	checkRCPossible(array, 0, 0)
	checkRCPossible(array, 0, 3)
	checkRCPossible(array, 0, 6)
	checkRCPossible(array, 3, 0)
	checkRCPossible(array, 3, 3)
	checkRCPossible(array, 3, 6)
	checkRCPossible(array, 6, 0)
	checkRCPossible(array, 6, 3)
	checkRCPossible(array, 6, 6)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if !array[i][j].isCertained {
				a := checkRowColumn(array, i, j)
				b := checkQuac(array, i, j)
				c := removeNotDuplicatedNums(a, b)
				if len(array[i][j].possibleNumbers) != 0 {
					c = removeNotDuplicatedNums(c, array[i][j].possibleNumbers)
				}
				if len(c) == 1 {
					addFoundNum(array, c[0], i, j, know)
				} else {
					array[i][j].possibleNumbers = c
				}
			}
		}
	}
	if temp==*know {
		//先不用这种判别方式
		//checkOnyOneForRow(array, know)
		//checkOnyOneForColumn(array, know)
		//回溯法
		return false
	}
	return true
}

//在一个宫里判断有没有可能唯一情况
func checkOnyOneForArea(array *[9][9]*Space, x_first, y_first int, know *int) {
	m := make(map[int][]*position)
	//做一个逆哈希表
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if !array[x_first+i][y_first+j].isCertained {
				for _, v := range array[x_first+i][y_first+j].possibleNumbers {
					if _, ok := m[v]; !ok {
						m[v] = []*position{}
					}
					m[v] = append(m[v], &position{
						x: x_first + i,
						y: y_first + j,
					})
				}
			}
		}
	}
	for k, v := range m {
		if len(v) == 1 {
			addFoundNum(array, k, v[0].x, v[0].y, know)
		}
	}
}

//在行列里判断有没有可能唯一情况
func checkOnyOneForRow(array *[9][9]*Space, know *int) {
	for i := 0; i < 9; i++ {
		m := make(map[int][]*position)
		//做一个逆哈希表\
		for j := 0; j < 9; j++ {
			if !array[i][j].isCertained {
				for _, v := range array[i][j].possibleNumbers {
					if _, ok := m[v]; !ok {
						m[v] = []*position{}
					}
					m[v] = append(m[v], &position{
						x: i,
						y: j,
					})
				}
			}
		}
		for k, v := range m {
			if len(v) == 1 {
				addFoundNum(array, k, v[0].x, v[0].y, know)
			}
		}
	}
}
func checkOnyOneForColumn(array *[9][9]*Space, know *int) {
	for j := 0; j < 9; j++ {
		m := make(map[int][]*position)
		//做一个逆哈希表\
		for i := 0; i < 9; i++ {
			if !array[i][j].isCertained {
				for _, v := range array[i][j].possibleNumbers {
					if _, ok := m[v]; !ok {
						m[v] = []*position{}
					}
					m[v] = append(m[v], &position{
						x: i,
						y: j,
					})
				}
			}
		}
		for k, v := range m {
			if len(v) == 1 {
				addFoundNum(array, k, v[0].x, v[0].y, know)
			}
		}
	}
}

//模糊性判断横竖列
func checkRCPossible(array *[9][9]*Space, x_first, y_first int) {
	m := make(map[int][]*position)
	//做一个逆哈希表
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if !array[x_first+i][y_first+j].isCertained {
				for _, v := range array[x_first+i][y_first+j].possibleNumbers {
					if _, ok := m[v]; !ok {
						m[v] = []*position{}
					}
					m[v] = append(m[v], &position{
						x: x_first + i,
						y: y_first + j,
					})
				}
			}
		}
	}
	for k, v := range m {
		//行
		vx := v[0].x
		vy := v[0].y
		isOnlyRow, isOnlyCol := true, true

		for i := 1; i < len(v); i++ {
			if v[i].x != vx {
				isOnlyRow = false
			}
			if v[i].y != vy {
				isOnlyCol = false
			}
		}
		if isOnlyRow {
			for i := 0; i < 9; i++ {
				if !array[vx][i].isCertained && (i < y_first || i > y_first+2) {
					array[vx][i].possibleNumbers = removeNums(array[vx][i].possibleNumbers, k)
				}
			}
		}
		if isOnlyCol {
			for i := 0; i < 9; i++ {
				if !array[i][vy].isCertained && (i < x_first || i > x_first+2) {
					array[i][vy].possibleNumbers = removeNums(array[i][vy].possibleNumbers, k)
				}
			}
		}
	}
}

//去除数组中的指定数字
func removeNums(a []int, x int) []int {
	if len(a) == 0 {
		return []int{}
	}
	i := 0
	for ; i < len(a); i++ {
		if a[i] == x {
			break
		}
	}
	if i == 0 {
		return a[1:len(a)]
	} else if i > len(a)-2 {
		return a[0:i]
	} else {
		return a[:i+copy(a[i:], a[i+1:])]
	}
}

//去重
func removeNotDuplicatedNums(a, b []int) []int {
	record := make([]int, 10)
	res := []int{}
	for _, v := range a {
		record[v]++
	}
	for _, v := range b {
		record[v]++
	}
	for i := 1; i < 10; i++ {
		if record[i] == 2 {
			res = append(res, i)
		}
	}
	return res
}